#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// 30. 串联所有单词的子串
class Solution1
{
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        unordered_map<string, int> hash1;
        for(auto& word : words) ++hash1[word];

        int m = words.size(), len = words[0].size(), n = s.size();
        vector<int> ret;
        for(int i = 0; i < len; ++i)
        {
            unordered_map<string, int> hash2;
            for(int left = i, right = i, cnt = 0; right + len <= n; right += len)
            {
                string in = s.substr(right, len);
                ++hash2[in];
                if(hash1.count(in) && hash2[in] <= hash1[in]) ++cnt;
                if(right - left + 1 > len * m)
                {
                    string out = s.substr(left, len);
                    if(hash1.count(out) && hash2[out] <= hash1[out]) --cnt;
                    --hash2[out];
                    left += len;
                }
                if(cnt == m) ret.push_back(left);
            }
        }

        return ret;
    }
};

// 904. 水果成篮
class Solution2
{
public:
    int totalFruit(vector<int>& fruits) 
    {
        unordered_map<int, int> m;
        int left = 0, right = 0, ret = 0, n = fruits.size();
        while(right < n)
        {
            ++m[fruits[right]];
            while(m.size() > 2)
            {
                --m[fruits[left]];
                if(m[fruits[left]] == 0) m.erase(fruits[left]);
                ++left;
            }
            ret = max(ret, right - left + 1);
            ++right;
        }
        return ret; 
    }
};

// LCR 017. 最小覆盖子串
class Solution3
{
public:
    string minWindow(string s, string t) 
    {
        int m[128]{};
        int kind = 0;
        for(char ch : t)
        {
            if(m[ch]++ == 0) ++kind;
        }

        int begin = -1, minLen = INT_MAX, left = 0, right = 0, n = s.size(), cnt = 0;
        int m2[128]{};
        while(right < n)
        {
            char in = s[right];
            if(++m2[in] == m[in]) ++cnt;
            while(cnt == kind)
            {
                if(right - left + 1 < minLen)
                {
                    minLen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if(m2[out]-- == m[out]) --cnt;
            }
            ++right;
        }

        if(begin == -1) return "";
        return s.substr(begin, minLen);
    }
};

// 395. 至少有 K 个重复字符的最长子串
class Solution4
{
public:
    int longestSubstring(string s, int k) 
    {
        int n = s.size();
        if(n < k) return 0;

        int ret = 0;
        for(int t = 1; t <= 26; ++t)
        {
            int left = 0, right = 0, total = 0, less = 0;
            int cnt[26]{};
            while(right < n)
            {
                char in = s[right] - 'a';
                ++cnt[in];
                if(cnt[in] == 1)
                {
                    ++total;
                    ++less;
                }

                if(cnt[in] == k) --less;

                while(total > t)
                {
                    char out = s[left] - 'a';
                    --cnt[out];
                    if(cnt[out] == k - 1) ++less;
                    if(cnt[out] == 0)
                    {
                        --total;
                        --less;
                    }

                    ++left;
                }

                if(less == 0) ret = max(ret, right - left + 1);

                ++right;
            }
        }

        return ret;
    }
};

// 424. 替换后的最长重复字符
class Solution5
{
public:
    int characterReplacement(string s, int k) 
    {
        int cnt[26]{};
        for(char ch : s) ++cnt[ch - 'A'];

        int n = s.size(), ret = 0;
        for(int i = 0; i < 26; ++i)
        {
            if(cnt[i] == 0) continue; 
            char ch = 'A' + i;
            int left = 0, right = 0, diff = 0;
            while(right < n)
            {
                if(s[right] != ch) ++diff;
                while(diff > k)
                {
                    if(s[left++] != ch) --diff;
                }
                ret = max(ret, right - left + 1);
                ++right;
            }
        }

        return ret;
    }
};